#include <iostream>
#include <algorithm>
#include "Compute.h"

using namespace std;


Compute::Compute(const set<string> &words) : wordsMap(vector<vector<Word>>(26)) {
    for (const string &w : words) {
        Word *word = new Word(w);
        this->wordsMap.at(word->getHeadLetter() - 'a').emplace_back(*word);
        int s = word->getHeadLetter() - 'a';
        int t = word->getTailLetter() - 'a';
        linkMap[s][t].push_back(*word);
        if (longestLink[s][t] == nullptr
            || word->getLength() > longestLink[s][t]->getLength()) {
            longestLink[s][t] = word;
        }
    }
}

//Compute::Compute(const set<std::string> &words, char rejected) : wordsMap(vector<vector<Word>>(26)) {
//    for (const string &w : words) {
//        if (::tolower(w[0]) == rejected) {
//            continue;
//        }
//        Word *word = new Word(w);
//        this->wordsMap.at(word->getHeadLetter() - 'a').emplace_back(*word);
//        int s = word->getHeadLetter() - 'a';
//        int t = word->getTailLetter() - 'a';
//        linkMap[s][t].push_back(*word);
//        if (longestLink[s][t] == nullptr
//            || word->getLength() > longestLink[s][t]->getLength()) {
//            longestLink[s][t] = word;
//        }
//    }
//}

//Compute::Compute(char **words, int len) : wordsMap(vector<vector<Word>>(26)) {
//    for (int i = 0; i < len; i++) {
//        Word *word = new Word(words[i]);
//        this->wordsMap.at(word->getHeadLetter() - 'a').emplace_back(*word);
//        int s = word->getHeadLetter() - 'a';
//        int t = word->getTailLetter() - 'a';
//        linkMap[s][t].push_back(*word);
//        if (longestLink[s][t] == nullptr
//            || word->getLength() > longestLink[s][t]->getLength()) {
//            longestLink[s][t] = word;
//        }
//    }
//}
//
//Compute::Compute(char **words, int len, char reject) : wordsMap(vector<vector<Word>>(26)) {
//    for (int i = 0; i < len; i++) {
//        if (::tolower(words[i][0]) == reject) {
//            continue;
//        }
//        Word *word = new Word(words[i]);
//        this->wordsMap.at(word->getHeadLetter() - 'a').emplace_back(*word);
//        int s = word->getHeadLetter() - 'a';
//        int t = word->getTailLetter() - 'a';
//        linkMap[s][t].push_back(*word);
//        if (longestLink[s][t] == nullptr
//            || word->getLength() > longestLink[s][t]->getLength()) {
//            longestLink[s][t] = word;
//        }
//    }
//}

bool Compute::hasCircle() {
    for (int i = 0; i < 26; i++) {
        for (Word &word : this->wordsMap.at(i)) {
            if (!word.checkCircleVisited) {
                int headLetter[26] = {0};
                if (hasCircle(headLetter, word)) {
                    return true;
                }
            }
        }
    }
    return false;
}

bool Compute::hasCircle(int headLetter[], Word &word) {
    headLetter[word.getHeadLetter() - 'a'] += 1;
    for (Word &w : this->wordsMap.at(word.getTailLetter() - 'a')) {
        if (word.str == w.str || word.checkCircleVisited) {
            continue;
        }
        if (headLetter[w.getTailLetter() - 'a'] != 0) {
            return true;
        }
        if (hasCircle(headLetter, w)) {
            return true;
        }
    }
    headLetter[word.getHeadLetter() - 'a'] -= 1;
    word.checkCircleVisited = true;
    return false;
}

vector<string> Compute::getAllChains() {
    auto *chains = new vector<string>();
    for (int i = 0; i < 26; i++) {
        for (Word &w : this->wordsMap.at(i)) {
            dfs(chains, w);
        }
    }
    return *chains;
}

void Compute::dfs(vector<string> *chains, Word &word) {
    if (word.genChainVisited) {
        return;
    }
    word.genChainVisited = true;
    word.chains.emplace_back(word.str);
    for (Word &w : this->wordsMap.at(word.getTailLetter() - 'a')) {
        if (word.str == w.str) {
            continue;
        }
        if (!w.genChainVisited) {
            dfs(chains, w);
        }
        for (string &s : w.chains) {
            word.chains.emplace_back(word.str + " " + s);
            chains->emplace_back(word.str + " " + s);
        }
    }
}

//string Compute::getMaxWordChainNotAllowCircle(const char h, const char t, const char j) {
//    int maxChainsLength = 0;
//    vector<string> *chains = new vector<string>();
//    if (h == 0) {
//        for (int i = 0; i < 26 && i != j - 'a'; i++) {
//            for (Word &w : this->wordsMap.at(i)) {
//                if (w.genChainVisited) {
//                    continue;
//                }
//                dfsMaxWordCHain(w, t);
//                if (maxChainsLength < w.maxChainsLength) {
//                    maxChainsLength = w.maxChainsLength;
//                    chains = &w.chains;
//                }
//            }
//        }
//    } else {
//        for (Word &w : this->wordsMap.at(h - 'a')) {
//            if (!w.genChainVisited) {
//                continue;
//            }
//            dfsMaxWordCHain(w, t);
//            if (maxChainsLength < w.maxChainsLength) {
//                maxChainsLength = w.maxChainsLength;
//                chains = &w.chains;
//            }
//        }
//    }
//    if (chains->size() == 1) {
//        return "The qualified word chain does not exist.";
//    } else {
//        string res = "";
//        for (string &c : *chains) {
//            res += c;
//        }
//        return res;
//    }
//}

void Compute::dfsMaxWordCHain(Word &word, const char t) {
    if (word.genChainVisited) {
        return;
    }
    word.genChainVisited = true;
    int max = 0;
    Word *maxNode = nullptr;
    for (Word &w : this->wordsMap.at(word.getTailLetter() - 'a')) {
        if (w.str == word.str) {
            continue;
        }
        if (!w.genChainVisited) {
            dfsMaxWordCHain(w, t);
        }
        if (max < w.maxChainsLength) {
            max = w.maxChainsLength;
            maxNode = &w;
        }
    }
    if (max == 0) {
        if (t == 0 || word.getTailLetter() == t) {
            word.setChainsWord(*new vector<string>, 0);
        }
    } else {
        word.setChainsWord(maxNode->chains, max);
    }
}

//string Compute::getMaxWordChainAllowCircle(const char h, const char t, const char j) {
//    return "";
//}

//string Compute::getMaxLetterChainNotAllowCircle(const char h, const char t, const char j) {
//    int maxLetter = 0;
//    vector<string> *chains = new vector<string>;
//    if (h == 0) {
//        for (int i = 0; i < 26 && i != j - 'a'; i++) {
//            for (Word &w : this->wordsMap.at(i)) {
//                if (w.genChainVisited) {
//                    continue;
//                }
//                dfsMaxLetterCHain(w, t);
//                if (maxLetter < w.maxLetterLength) {
//                    maxLetter = w.maxLetterLength;
//                    chains = &w.chains;
//                }
//            }
//        }
//    } else {
//        for (Word &w : this->wordsMap.at(h - 'a')) {
//            if (w.genChainVisited) {
//                continue;
//            }
//            dfsMaxLetterCHain(w, t);
//            if (maxLetter < w.maxLetterLength) {
//                maxLetter = w.maxLetterLength;
//                chains = &w.chains;
//            }
//        }
//    }
//    if (chains->size() == 1) {
//        return "The qualified word chain does not exist.";
//    } else {
//        string res = "";
//        for (string &c : *chains) {
//            res += c;
//        }
//        return res;
//    }
//}

//void Compute::dfsMaxLetterCHain(Word &word, const char t) {
//    if (word.genChainVisited) {
//        return;
//    }
//    word.genChainVisited = true;
//    int max = 0;
//    Word *maxNode = nullptr;
//    for (Word &w : this->wordsMap.at(word.getTailLetter() - 'a')) {
//        if (w.str == word.str) {
//            continue;
//        }
//        if (!w.genChainVisited) {
//            dfsMaxWordCHain(w, t);
//        }
//        if (max < w.maxLetterLength) {
//            max = w.maxLetterLength;
//            maxNode = &w;
//        }
//    }
//    if (max == 0) {
//        if (t == 0 || word.getTailLetter() == t) {
//            word.setChainsLetter(*new vector<string>, 0);
//        }
//    } else {
//        word.setChainsLetter(maxNode->chains, max);
//    }
//}

std::vector<int> Compute::topologicalSort() {
    int in_degree[26] = {0};
    for (int i = 0; i < 26; i++) {
        for (int j = 0; j < 26; j++) {
            in_degree[i] += (int) linkMap[j][i].size();
        }
    }
    vector<int> res;
    stack<int> stack;
    for (int i = 0; i < 26; i++) {
        if (in_degree[i] == 0) {
            stack.push(i);
        }
    }
    while (!stack.empty()) {
        int i = stack.top();
        res.push_back(i);
        stack.pop();
        for (int j = 0; j < 26; j++) {
            if ((int) linkMap[i][j].size() == 0) {
                continue;
            }
            in_degree[j] -= (int) linkMap[i][j].size();
            if (in_degree[j] == 0) {
                stack.push(j);
            }
        }
    }
    return res;
}

std::vector<int> Compute::topologicalSortForScc() {
    int in_degree[26] = {0};
    int n_scc = (int) sccList.size();
    for (int i = 0; i < n_scc; i++) {
        for (int j = 0; j < n_scc; j++) {
            in_degree[i] += (int) sccLinkMap[j][i].size();
        }
//        cout << i << " -- " << in_degree[i] << endl;
    }
    vector<int> res;
    stack<int> stack;
    for (int i = 0; i < n_scc; i++) {
        if (in_degree[i] == 0) {
            stack.push(i);
        }
    }
    while (!stack.empty()) {
        int i = stack.top();
        res.push_back(i);
        stack.pop();
        for (Word word : sccLinkList[i]) {
            int j = node2scc[word.getTailLetter() - 'a'];
            in_degree[j] -= (int) sccLinkMap[i][j].size();
            if (j != i && in_degree[j] == 0) {
                stack.push(j);
            }
        }
    }
//    for (int i : res) {
//        cout << i << ": ";
//        for (int node : sccList[i].getNodes()) {
//            cout << (char)('a' + node) << " ";
//        }
//        cout << endl;
//    }
    return res;
}

//WordChain Compute::getDiameter(int lengthType) {
//    int dp[26] = {0}, dp_max = 0;
//    WordChain *rec[26] = { nullptr }, *res = new WordChain();
//    vector<int> indices = topologicalSort();
//    for (int dst : indices) {
//        for (int src = 0; src < 26; src++) {
//            if (longestLink[src][dst] == nullptr) {
//                continue;
//            }
//            Word word = *longestLink[src][dst];
//            int dist = lengthType == 0 ? 1 : word.getLength();
//            if (dp[src] + dist > dp[dst]) {
//                dp[dst] = dp[src] + dist;
//                delete rec[dst];
//                rec[dst] = rec[src] == nullptr ? new WordChain() : new WordChain(*rec[src]);
//                rec[dst]->append(word);
//            }
//            if (dp[src] + dist > dp_max && rec[src] != nullptr && rec[src]->getWordNum() > 0) {
//                dp_max = dp[src] + dist;
//                delete res;
//                res = rec[src] == nullptr ? new WordChain() : new WordChain(*rec[src]);
//                res->append(word);
//            }
//        }
//    }
//    return *res;
//}
//
//WordChain Compute::getLongestPathTo(char tail, int lengthType) {
//    int dp[26] = {0}, dp_max = 0;
//    WordChain *rec[26] = {nullptr}, *res = new WordChain();
//    vector<int> indices = topologicalSort();
//    for (int dst : indices) {
//        for (int src = 0; src < 26; src++) {
//            if (longestLink[src][dst] == nullptr) {
//                continue;
//            }
//            Word word = *longestLink[src][dst];
//            int dist = lengthType == 0 ? 1 : word.getLength() ;
//            if (dp[src] + dist > dp[dst]) {
//                dp[dst] = dp[src] + dist;
//                delete rec[dst];
//                rec[dst] = rec[src] == nullptr ? new WordChain() : new WordChain(*rec[src]);
//                rec[dst]->append(word);
//            }
//            if (dst == ::tolower(tail) - 'a'
//                    && dp[src] + dist > dp_max
//                    && rec[src] != nullptr
//                    && rec[src]->getWordNum() > 0) {
//                dp_max = dp[src] + dist;
//                delete res;
//                res = rec[src] == nullptr ? new WordChain() : new WordChain(*rec[src]);
//                res->append(word);
//            }
//        }
//    }
//    return *res;
//}
//
//WordChain Compute::getLongestPathFrom(char head, int lengthType) {
//    int dp[26] = {0}, dp_max = 0;
//    WordChain *rec[26] = {nullptr}, *res = new WordChain();
//    vector<int> indices = topologicalSort();
//    for (int i = 25; i >= 0; i--) {
//        int src = indices[i];
//        for (int dst = 0; dst < 26; dst++) {
//            if (longestLink[src][dst] == nullptr) {
//                continue;
//            }
//            Word word = *longestLink[src][dst];
//            int dist = lengthType == 0 ? 1 : word.getLength();
//            if (dist + dp[dst] > dp[src]) {
//                dp[src] = dist + dp[dst];
//                delete rec[src];
//                rec[src] = rec[dst] == nullptr ? new WordChain() : new WordChain(*rec[dst]);
//                rec[src]->insertHead(word);
//            }
//            if (src == head - 'a' && dist + dp[dst] > dp_max
//                    && rec[dst] != nullptr && rec[dst]->getWordNum() > 0) {
//                dp_max = dist + dp[dst];
//                delete res;
//                res = rec[dst] == nullptr ? new WordChain() : new WordChain(*rec[dst]);
//                res->insertHead(word);
//            }
//        }
//    }
//    return *res;
//}
//
//WordChain Compute::getLongestPathBetween(char head, char tail, int lengthType) {
//    int dp[26], dp_max = 0;
//    WordChain *rec[26] = { nullptr }, *res = new WordChain();
//    for (int & i : dp) {
//        i = -1;
//    }
//    dp[::tolower(head) - 'a'] = 0;
//    vector<int> indices = topologicalSort();
//    for (int dst : indices) {
//        for (int src = 0; src < 26; src++) {
//            if (longestLink[src][dst] == nullptr || dp[src] < 0) {
//                continue;
//            }
//            Word word = *longestLink[src][dst];
//            int dist = lengthType == 0 ? 1 : word.getLength();
//            if (dp[src] + dist > dp[dst]) {
//                dp[dst] = dp[src] + dist;
//                delete rec[dst];
//                rec[dst] = rec[src] == nullptr ? new WordChain() : new WordChain(*rec[src]);
//                rec[dst]->append(word);
//            }
//            if (dst == tail - 'a' && dp[src] + dist > dp_max && rec[src] != nullptr && rec[src]->getWordNum() > 0) {
//                dp_max = dp[src] + dist;
//                delete res;
//                res = rec[src] == nullptr ? new WordChain() : new WordChain(*rec[src]);
//                res->append(word);
//            }
//        }
//    }
//    return *res;
//}

void Compute::getScc() {
    int num = 1, dfn[26] = { 0 }, low[26] = { 0 };
    auto *stack = new vector<int>();
    for (int i = 0; i < 26; i++) {
        if (dfn[i] == 0) {
            tarjan(i, &num, dfn, low, stack);
        }
    }
    delete stack;
    for (int i = 0; i < 26; i++) {
        for (int j = 0; j < 26; j++) {
            if (node2scc[i] == node2scc[j]) {
                continue; // i, j in the same SCC
            }
            for (const Word& word : linkMap[i][j]) {
                sccLinkList[node2scc[i]].push_back(word);
                sccLinkMap[node2scc[i]][node2scc[j]].push_back(word);
            }
            longestBridge[i][j] = longestLink[i][j];
        }
    }
    for (auto & i : sccList) {
        i.searchPaths();
    }
}

void Compute::tarjan(int node, int *num, int *dfn, int *low, vector<int> *stack) {
    dfn[node] = low[node] = (*num)++;
    stack->push_back(node);
    for (int next = 0; next < 26; next++) {
        if (linkMap[node][next].empty()) {
            continue;
        }
        if (dfn[next] == 0) {
            tarjan(next, num, dfn, low, stack);
            low[node] = low[next] < low[node] ? low[next] : low[node];
        } else if (std::count(stack->begin(), stack->end(), next) > 0) {
            low[node] = dfn[next] < low[node] ? dfn[next] : low[node];
        }
    }

    if (dfn[node] == low[node]) {
        auto *scc = new SCComponent();
        int top;
        do {
            top = (*stack)[stack->size() - 1];
            stack->pop_back();
            scc->addNode(top);
            node2scc[top] = (int) sccList.size();
        } while(top != node);
        vector<int> nodes = scc->getNodes();
        for (int i : nodes) {
            for (int j : nodes) {
                for (const Word& word : this->linkMap[i][j]) {
                    scc->addEdge(word);
                }
                longestLink[i][j] = nullptr;
            }
        }
        sccList.push_back(*scc);
    }
}

WordChain Compute::getDiameterWithCircle(int lengthType) {
    int dp_in[26] = {0}, dp_out[26] = {0}, dp_max = 0;
    WordChain *rec_in[26] = { nullptr }, *rec_out[26] = { nullptr }, *res = new WordChain();

    getScc();
    vector<int> indices = topologicalSortForScc();
    // for each SCC
    for (int index : indices) {
        // update dp_in of all nodes in this SCC
        for (int dst : sccList[index].getNodes()) {
            for (int src = 0; src < 26; src++) {
                Word *word = longestBridge[src][dst];
                if (word == nullptr) {
                    continue;
                }
                int dist = lengthType == 0 ? 1 : word->getLength();
                if (dp_out[src] + dist > dp_in[dst]) {
                    dp_in[dst] = dp_out[src] + dist;
                    delete rec_in[dst];
                    rec_in[dst] = rec_out[src] == nullptr ? new WordChain() : new WordChain(*rec_out[src]);
                    rec_in[dst]->append(*word);
                }
                if (dp_out[src] + dist > dp_max
                        && rec_out[src] != nullptr
                        && rec_out[src]->getWordNum() > 0) {
                    dp_max = dp_out[dst] + dist;
                    delete res;
                    res = new WordChain(*rec_out[src]);
                    res->append(*word);
//                    cout << " in => " << dp_max << " " << res->toString() << endl;
                }
            }
        }
        // update dp_out of all nodes in this SCC
        for (int dst : sccList[index].getNodes()) {
            // 更新dp_out
            for (int src : sccList[index].getNodes()) {
                WordChain path = lengthType == 0 ? sccList[index].getMostPathBetween(src, dst)
                                                 : sccList[index].getLongestPathBetween(src, dst);
                int dist = lengthType == 0 ? path.getWordNum() : path.getLetterNum();
                if (dp_in[src] + dist > dp_out[dst]) {
                    dp_out[dst] = dp_in[src] + dist;
                    delete rec_out[dst];
                    rec_out[dst] = rec_in[src] == nullptr ? new WordChain() : new WordChain(*rec_in[src]);
                    rec_out[dst]->append(path);
                }
                if (dp_in[src] + dist > dp_max &&
                        (rec_out[dst] == nullptr ? 0 : rec_out[dst]->getWordNum()) + path.getWordNum() > 1) {
                    dp_max = dp_in[src] + dist ;
                    delete res;
                    res = rec_in[src] == nullptr ? new WordChain() : new WordChain(*rec_in[src]);
                    res->append(path);
//                    cout << " out => " << dp_max << " " << res->toString() << endl;
                }
            }
        }
    }
//    for (int i = 0; i < 26; i++) {
//        if (rec_in[i] != nullptr) {
//            cout << dp_in[i] << ": in " << rec_in[i]->toString() << endl;
//        }
//        if (rec_out[i] != nullptr) {
//            cout << dp_out[i] << ": out " << rec_out[i]->toString() << endl;
//        }
//    }
//    cout << dp_max << ": res " << res->toString() << endl;
    return *res;
}

WordChain Compute::getLongestPathWithCirCleTo(char tail, int lengthType) {
    getScc();

    int dp_in[26] = {0}, dp_out[26] = {0}, dp_max = 0;
    WordChain *rec_in[26] = {nullptr}, *rec_out[26] = {nullptr}, *res = new WordChain();
    vector<int> indices = topologicalSortForScc();
    // for each SCC
    for (int index : indices) {
        // update dp_in of all nodes in this SCC
        for (int dst : sccList[index].getNodes()) {
            for (int src = 0; src < 26; src++) {
                Word *word = longestBridge[src][dst];
                if (word == nullptr) {
                    continue;
                }
                int dist = lengthType == 0 ? 1 : word->getLength();
                if (dp_out[src] + dist > dp_in[dst]) {
                    dp_in[dst] = dp_out[src] + dist;
                    delete rec_in[dst];
                    rec_in[dst] = rec_out[src] == nullptr ? new WordChain() : new WordChain(*rec_out[src]);
                    rec_in[dst]->append(*word);
                }
                if (dst == ::tolower(tail) - 'a' && dp_out[src] + dist > dp_max
                        && rec_out[src] != nullptr && rec_out[src]->getWordNum() > 0) {
                    dp_max = dp_out[src] + dist;
                    delete res;
                    res = rec_out[src] == nullptr ? new WordChain() : new WordChain(*rec_out[src]);
                    res->append(*word);
                }
            }
        }
        // update dp_out of all nodes in this SCC
        for (int dst : sccList[index].getNodes()) {
            // 更新dp_out
            for (int src : sccList[index].getNodes()) {
                WordChain path = lengthType == 0 ? sccList[index].getMostPathBetween(src, dst)
                                                 : sccList[index].getLongestPathBetween(src, dst);
                int dist = lengthType == 0 ? path.getWordNum() : path.getLetterNum();
                if (dp_in[src] + dist > dp_out[dst]) {
                    dp_out[dst] = dp_in[src] + dist;
                    delete rec_out[dst];
                    rec_out[dst] = rec_in[src] == nullptr ? new WordChain() : new WordChain(*rec_in[src]);
                    rec_out[dst]->append(path);
                }
                if (dst == ::tolower(tail) - 'a' && dp_in[src] + dist > dp_max
                        && (rec_out[dst] == nullptr ? 0 : rec_out[dst]->getWordNum()) + path.getWordNum() > 1) {
                    dp_max = dp_in[src] + dist;
                    delete res;
                    res = rec_in[src] == nullptr ? new WordChain() : new WordChain(*rec_in[src]);
                    res->append(path);
                }
            }
        }
    }
//    for (int i = 0; i < 26; i++) {
//        if (rec_in[i] != nullptr) {
//            cout << dp_in[i] << ": in " << rec_in[i]->toString() << endl;
//        }
//        if (rec_out[i] != nullptr) {
//            cout << dp_out[i] << ": out " << rec_out[i]->toString() << endl;
//        }
//    }
    return *res;
}

WordChain Compute::getLongestPathWithCirCleFrom(char head, int lengthType) {
    int dp_in[26] = {0}, dp_out[26] = {0}, dp_max = 0;
    WordChain *rec_in[26] = { nullptr }, *rec_out[26] = { nullptr }, *res = new WordChain();

    getScc();

    for (int i = 0; i < 26; i++) {
        dp_in[i] = dp_out[i] = -1;
    }
    // 初始化起点SCC
    SCComponent sourceSCC = sccList[node2scc[::tolower(head) - 'a']];
    for (int node : sourceSCC.getNodes()) {
        WordChain chain = lengthType == 0 ? sourceSCC.getLongestPathBetween(::tolower(head) - 'a', node)
                                          : sourceSCC.getMostPathBetween(::tolower(head) - 'a', node);
        dp_out[node] = lengthType == 0 ? chain.getWordNum() : chain.getLetterNum();
        rec_out[node] = new WordChain(chain);
        if (dp_out[node] > dp_max && rec_out[node]->getWordNum() > 1) {
            dp_max = dp_out[node];
            delete res;
            res = new WordChain(*rec_out[node]);
        }
    }

    vector<int> indices = topologicalSortForScc();
    // for each SCC
    for (int index : indices) {
        // update dp_in of all nodes in this SCC
        for (int dst : sccList[index].getNodes()) {
            for (int src = 0; src < 26; src++) {
                Word *word = longestBridge[src][dst];
                if (word == nullptr || dp_out[src] < 0) {
                    continue;
                }
                int dist = lengthType == 0 ? 1 : word->getLength();
                if (dp_out[src] + dist > dp_in[dst]) {
                    dp_in[dst] = dp_out[src] + dist;
                    delete rec_in[dst];
                    rec_in[dst] = rec_out[src] == nullptr ? new WordChain() : new WordChain(*rec_out[src]);
                    rec_in[dst]->append(*word);
                }
                if (dp_out[src] + dist > dp_max && rec_out[src] != nullptr && rec_out[src]->getWordNum() > 0) {
                    dp_max = dp_out[src] + dist;
                    delete res;
                    res = new WordChain(*rec_out[src]);
                    res->append(*word);
                }
            }
        }
        // update dp_out of all nodes in this SCC
        for (int dst : sccList[index].getNodes()) {
            // 更新dp_out
            for (int src : sccList[index].getNodes()) {
                WordChain path = lengthType == 0 ? sccList[index].getMostPathBetween(src, dst)
                                                 : sccList[index].getLongestPathBetween(src, dst);
                if (dp_in[src] < 0) {
                    continue;
                }
                int dist = lengthType == 0 ? path.getWordNum() : path.getLetterNum();
                if (dp_in[src] + dist > dp_out[dst]) {
                    dp_out[dst] = dp_in[src] + dist;
                    delete rec_out[dst];
                    rec_out[dst] = rec_in[src] == nullptr ? new WordChain() : new WordChain(*rec_in[src]);
                    rec_out[dst]->append(path);
                }
                if (dp_in[src] + dist > dp_max
                    && (rec_out[dst] == nullptr ? 0 : rec_out[dst]->getWordNum()) + path.getWordNum() > 1) {
                    dp_max = dp_in[src] + dist;
                    delete res;
                    res = rec_in[src] == nullptr ? new WordChain() : new WordChain(*rec_in[src]);
                    res->append(path);
                }
            }
        }
    }
//    for (int i = 0; i < 26; i++) {
//        if (rec_in[i] != nullptr) {
//            cout << dp_in[i] << ": in " << rec_in[i]->toString() << endl;
//        }
//        if (rec_out[i] != nullptr) {
//            cout << dp_out[i] << ": out " << rec_out[i]->toString() << endl;
//        }
//    }
    return *res;
}

WordChain Compute::getLongestPathWithCirCleBetween(char head, char tail, int lengthType) {
    int dp_in[26] = {0}, dp_out[26] = {0}, dp_max = 0;
    WordChain *rec_in[26] = { nullptr }, *rec_out[26] = { nullptr }, *res = new WordChain();

    getScc();

    for (int i = 0; i < 26; i++) {
        dp_in[i] = dp_out[i] = -1;
    }
    SCComponent sourceSCC = sccList[node2scc[::tolower(head) - 'a']];
    for (int node : sourceSCC.getNodes()) {
        WordChain chain = lengthType == 0 ? sourceSCC.getLongestPathBetween(::tolower(head) - 'a', node)
                                          : sourceSCC.getMostPathBetween(::tolower(head) - 'a', node);
        dp_out[node] = lengthType == 0 ? chain.getWordNum() : chain.getLetterNum();
        rec_out[node] = new WordChain(chain);
        if (node == ::tolower(tail) - 'a' && dp_out[node] > dp_max && rec_out[node]->getWordNum() > 1) {
            dp_max = dp_out[node];
            delete res;
            res = new WordChain(*rec_out[node]);
        }
    }

    vector<int> indices = topologicalSortForScc();
    // for each SCC
    for (int index : indices) {
        // update dp_in of all nodes in this SCC
        for (int dst : sccList[index].getNodes()) {
            for (int src = 0; src < 26; src++) {
                Word *word = longestBridge[src][dst];
                if (word == nullptr || dp_out[src] < 0) {
                    continue;
                }
                int dist = lengthType == 0 ? 1 : word->getLength();
                if (dp_out[src] + dist > dp_in[dst]) {
                    dp_in[dst] = dp_out[src] + dist;
                    delete rec_in[dst];
                    rec_in[dst] = rec_out[src] == nullptr ? new WordChain() : new WordChain(*rec_out[src]);
                    rec_in[dst]->append(*word);
                }
                if (dst == ::tolower(tail) - 'a'
                        && dp_out[src] + dist > dp_max
                        && rec_out[src] != nullptr
                        && rec_out[src]->getWordNum() > 0) {
                    dp_max = dp_out[src] + dist;
                    delete res;
                    res = rec_out[src] == nullptr ? new WordChain() : new WordChain(*rec_out[src]);
                    res->append(*word);
                }
            }
        }
        // update dp_out of all nodes in this SCC
        for (int dst : sccList[index].getNodes()) {
            // 更新dp_out
            for (int src : sccList[index].getNodes()) {
                WordChain path = lengthType == 0 ? sccList[index].getMostPathBetween(src, dst)
                                                 : sccList[index].getLongestPathBetween(src, dst);
                if (dp_in[src] < 0) {
                    continue;
                }
                int dist = lengthType == 0 ? path.getWordNum() : path.getLetterNum();
                if (dp_in[src] + dist > dp_out[dst]) {
                    dp_out[dst] = dp_in[src] + dist;
                    delete rec_out[dst];
                    rec_out[dst] = rec_in[src] == nullptr ? new WordChain() : new WordChain(*rec_in[src]);
                    rec_out[dst]->append(path);
                }
                if (dst == ::tolower(tail) - 'a'
                        && dp_in[src] + dist > dp_max
                        && (rec_in[src] == nullptr ? 0 : rec_in[src]->getWordNum()) + path.getWordNum() > 1) {
                    dp_max = dp_in[src] + dist;
                    delete res;
                    res = rec_in[src] == nullptr ? new WordChain() : new WordChain(*rec_in[src]);
                    res->append(path);
                }
            }
        }
    }
//    for (int i = 0; i < 26; i++) {
//        if (rec_in[i] != nullptr) {
//            cout << dp_in[i] << ": in " << (char)('a' + i) << rec_in[i]->toString() << endl;
//        }
//        if (rec_out[i] != nullptr) {
//            cout << dp_out[i] << ": out " << (char)('a' + i) << rec_out[i]->toString() << endl;
//        }
//    }
//    cout << res->toString() << endl;
    return *res;
}
